package com.code.leetcode._202507;

import java.util.*;

/**
 * 40. 组合总和 ，难度为 中等。
 ***/
public class CombinationSum {
    /**
     * 给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合
     * candidates中的每个数组在每个组合中只能使用一次
     * 所有的数字都是正整数
     * 解集不能包含重复的组合
     * 示例1：输入：candidates=[10,1,2,7,6,1,5],target =8
     * 所求解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]
     * 示例2：输入：candidates=[2,5,2,1,2],target = 5,
     * 所求解集为：[[1,2,2],[5]]
     **/
    public static void main(String[] args) {
        CombinationSum  c = new CombinationSum();
        System.out.println(c.combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8));
    }

    /**
     * 由于我们需要求出所有和为target的组合，并且每个数只能使用一次，因此我们使用递归+回溯的方法来解决这个问题
     * 1、我们用dfs(pos,rest)表示递归的函数，其中pos表示我们当前递归到了数组candidates中的第pos个数，
     * 而rest表示我们还需要选择和为rest的数放入列表作为一个组合
     * 2、对于当前的第pos个数，我们有两种方法：选或者不选，如果我们选了这个数，那么我们调用dfs(pos+1,rest-candidates[pos])
     * 进行递归，注意这里必须满足，rest>=candidates[pos]。如果我们不选这个数，我们调用dfs(pos+1,rest)进行递归
     * 3、在某次递归开始钱，如果rest的值为0，说明我们找到了一个和为target的组合，将起放入答案中，每次调用递归函数前，
     * 如果我们选了这个数，就需要将其放入队列的末尾，该列表中存储了我们选的所有数。在回溯时，如果我们选了那个数，就要将其从队列的末尾删除
     *
     * 上述的算法就是一个标准的递归+回溯算法，但是它并不适用于本题，这是因为题目描述中规定了解题不能包含重复的组合，
     * 而上述的算法中并没有去除重复的组合。
     * 因此我们需要改进上述算法，在求出组合的过程中就进行去重的操作。我们可以考虑将相同的数放在一起进行处理，也就是说，如果数x出现了y次，
     * 那么在递归时一次性地处理他们，即分别调用选择0,1,....,y次x的递归函数，这样我们就不会得到重复的组合。具体的：
     * 1、我们使用一个哈希映射(hashmap)统计数组candidates中每个数出现的次数，在统计完成之后，我们将结果放入一个列表freq中，方便后续的递归使用
     * 列表freq的长度即为数组candidates中不同的个数，其中的每一项对应这哈希映射中的一个键值对，即某个数以及他出现的次数
     * 2、在递归时，对于当前的第pos个数，它的值为freq[pos][0]，出现的次数为freq[pos][1]，那么我们可以调用dfs(pos+1,rest-i*freq[pos][0])
     * 即我们选择了这个数的i次。这里i不能大于这个数出现的次数，并且i*freq[pos][0]也不能大于rest。同时，我们需要将i个freq[pos][0]放入列表中
     * 这样一来，我们就可以不重复的枚举所有的组合了
     * 我们还可以选择进行优化，一种时比较常用的优化方法时，将freq根据从哪个小到大排序，这样我们在递归时会选择小的数，在选择大的数。这样做的好处是，
     * 当我们递归呆dfs(pos,rest)时，如果freq[pos][0]以及大于rest，那么后面还没有递归到的数也都大于rest，这样就说明不可能在选择若干个和为
     * rest的数放入列表了
     **/
    List<int[]> freq = new ArrayList<>();//数组去重后的个数 list的数组内容是[元素,数量]
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> sequence = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);//对数组进行排序
        for (int num : candidates) {
            int size = freq.size();
            //因为是有序数组，所以只需要跟前一个num进行比较就可以了
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0,target);
        return ans;
    }

    public void dfs(int pos, int rest) {
        if (rest == 0) {//如果rest为0表示满足了条件了，返回选择好的组合
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        //表示当前的数据用完了
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }
        dfs(pos + 1, rest);
        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; i++) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; i++) {
            sequence.remove(sequence.size() - 1);
        }
    }
}
